package sort.memory;

/**
 * 快速排序
 * @author：涂有
 * @date 2017年11月26日 下午8:49:17
 */
public class QuickSort {

	public static void sort(int[] a){
		sort(a, 0, a.length - 1, a.length >> 1);
	}
	
	protected static void sort(int[] a, int start, int end, int middle){
		if(start >= end) return;
		
		int pivot = adjust(a, start-1, end, middle);
		sort(a, start, pivot - 1, (start + pivot - 1) >> 1);
		sort(a, pivot + 1, end, (pivot + end + 1) >> 1);
	}
	
	public static int adjust(int[] a, int start, int end, int middle){
		int i = start;
		int j = end;
		int middleValue = a[middle];
		SortUtil.swap(a, middle, end); //把轴值放到最后，作为start右移监视哨
		while(i < j){
			while(a[++i] < middleValue); //不用判断出界，因为i移动到最后一位时，必定i > j导致退出循环
			while((j != i) && a[--j] > middleValue); //end先减，可以跨过监视哨
			SortUtil.swap(a, i, j);
		}
		SortUtil.swap(a, i, end); //把轴值放到轴点
		return i;
	}
}
